geometric graph theory Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geome ...

, a convex embedding of a graph is an embedding of the graph into a

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...

, with its vertices represented as points and its edges as line segments, so that all of the vertices outside a specified subset belong to the convex hull of their neighbors. More precisely, if

X

is a subset of the vertices of the graph, then a convex

X

-embedding embeds the graph in such a way that every vertex either belongs to

X

or is placed within the convex hull of its neighbors. A convex embedding into

d

-dimensional Euclidean space is said to be in

general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that are ...

if every subset

S

of its vertices spans a subspace of dimension

\min(d,, S, -1)

. Convex embeddings were introduced by

W. T. Tutte William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...

in 1963. Tutte showed that if the outer face

F

of a planar graph is fixed to the shape of a given convex polygon in the plane, and the remaining vertices are placed by solving a system of linear equations describing the behavior of ideal springs on the edges of the graph, then the result will be a convex

F

-embedding. More strongly, every face of an embedding constructed in this way will be a convex polygon, resulting in a convex drawing of the graph. Beyond planarity, convex embeddings gained interest from a 1988 result of Nati Linial,

László Lovász László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He wa ...

, and

Avi Wigderson Avi Wigderson ( he, אבי ויגדרזון; born 9 September 1956) is an Israeli mathematician and computer scientist. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jerse ...

that a graph is -vertex-connected if and only if it has a

(k-1)

-dimensional convex

S

-embedding in general position, for some

S

k

of its vertices, and that if it is -vertex-connected then such an embedding can be constructed in polynomial time by choosing

S

to be any subset of

k

vertices, and solving Tutte's system of linear equations. One-dimensional convex embeddings (in general position), for a specified set of two vertices, are equivalent to

bipolar orientation In graph theory, a bipolar orientation or ''st''-orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that causes the graph to become a directed acyclic graph with a single source ''s'' and a single sink ' ...

s of the given graph.

References

{{reflist, refs= {{citation , last1 = Linial , first1 = N. , author1-link = Nati Linial , last2 = Lovász , first2 = L. , author2-link = László Lovász , last3 = Wigderson , first3 = A. , author3-link = Avi Wigderson , doi = 10.1007/BF02122557 , issue = 1 , journal = Combinatorica , mr = 951998 , pages = 91–102 , title = Rubber bands, convex embeddings and graph connectivity , volume = 8 , year = 1988 {{citation , last = Tutte , first = W. T. , authorlink = W. T. Tutte , title = How to draw a graph , journal = Proceedings of the London Mathematical Society , volume = 13 , year = 1963 , pages = 743–767 , mr = 0158387 , doi = 10.1112/plms/s3-13.1.743. Geometric graph theory